import java.util.*;

public class Test {
    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,49,37};
        testHeap.initElem(array);
        testHeap.createHeap();
        testHeap.offer(80);
        System.out.println("=============");
        int[] ret = maxK(array,3);
        System.out.println(Arrays.toString(ret));
    }
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        //O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);
        for (int x: arr) {
            minHeap.offer(x);
        }
        //K * LOGN
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    /**
     * 前K个最大的元素
     * N*logK
     */
    public static int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //1、遍历数组的前K个 放到堆当中 K * logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //2、遍历剩下的K-1个，每次和堆顶元素进行比较
        // 堆顶元素 小的时候，就出堆。  (N-K) * Logk
        for (int i = k; i < arr.length; i++) {
            int val = minHeap.peek();
            if(val < arr[i]) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    //////////////////////////////////////////////////////////////////


    class Student implements Comparable<Student>{
        public int age;
        public String name;

        public Student(String name,int age) {
            this.name = name;
            this.age = age;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Student student = (Student) o;
            return age == student.age && Objects.equals(name, student.name);
        }

        @Override
        public int hashCode() {//此方法一般与equals方法成对出现。目前作用未知
            return Objects.hash(age, name);
        }

        @Override
        public int compareTo(Student o) {
            return this.age - o.age;
            //return o.age - this.age;//大根堆了
        }
    }

    class NameComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o1.name.compareTo(o2.name);
        }
    }
    class AgeComparator implements Comparator<Student> {

        @Override
        public int compare(Student o1, Student o2) {
            return o2.age-o1.age;
        }
    }

    class Incmp implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }
}
